package com.chapter16;

import java.math.BigDecimal;

public class SynthesizeExpression {

	
	private BigDecimal getRemval(int[] exp,int index,BigDecimal cur){
		BigDecimal val=new BigDecimal("0");
		BigDecimal ten=new BigDecimal("10");
		for(int i=index;i<exp.length;i++){
			BigDecimal c=new BigDecimal(""+exp[i]);
			val=val.multiply(ten);
			val=val.add(c);
		}
		return val;
	}
	public String getExpression(int[] exp,int index,String k,BigDecimal cur){
		BigDecimal rem=getRemval(exp,index,cur);
		if(cur.multiply(rem).toString().equals(k))
			return cur.toString()+"*"+rem.toString();
		if(cur.add(rem).toString().equals(k))
			return cur.toString()+"+"+rem.toString();
		
		
		BigDecimal val=new BigDecimal("0");
		BigDecimal ten=new BigDecimal("10");
		for(int i=index;i<exp.length-1;i++){
			BigDecimal curr=new BigDecimal(""+exp[i]);
			val=val.multiply(ten);
			val=val.add(curr);
			
			String byAdd=getExpression(exp,i+1,k,curr.add(cur));
			String byMul=getExpression(exp,i+1,k,curr.multiply(cur));
			if(!(byAdd==null && byMul==null))-
					return null;
			return (byAdd==null)?byMul:byAdd;
		}
		return null;
	}
	
	public String getExpressionPost(int[] exp,int index,String k,BigDecimal cur){
		BigDecimal rem=getRemval(exp,index,cur);
		if(cur.multiply(rem).toString().equals(k))
			return cur.toString()+"*"+rem.toString();
		if(cur.add(rem).toString().equals(k))
			return cur.toString()+"+"+rem.toString();
		
		
		BigDecimal val=new BigDecimal("0");
		BigDecimal ten=new BigDecimal("10");
		for(int i=index;i<exp.length-1;i++){
			String ex=getExpression(exp,i,k);
			BigDecimal bg=new BigDecimal(ex);
			BigDecimal cur=new BigDecimal(""+exp[i]);
			val=val.multiply(ten);
			val=val.add(cur);
			
			
		}
		return "null";
	}
}
